The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In internetworks such as the public Internet, to send a packet from one endpoint host to another, the sending host only needs to place an internet protocol (IP) address owned by the other host into the packet and relies on a network of elements such as routers, switches, bridges and hubs for actual delivery. An IP address can share a prefix that is assigned by a service provider, or provisioned by an organization owning the site of which the host is a part, or directly obtained from American Registry for Internet Numbers (ARIN). A prefix essentially is a subspace within the space of all possible IP addresses, and may encompass one or more local area networks (LANs).
The process of physically moving packets by routers, switches, bridges and hubs from a source to a destination is called forwarding. Typically, switches, bridges and hubs work at layer 1 or 2 of the Open System Interconnection (OSI) model and are invisible to hosts sending packets at layer 3 using logical IP addresses. Routers, on the other hand, use one or more layer 3 routing protocols to exchange route information and maintain route tables comprising best paths to various destinations. The destinations in the route table can be prefixes as well as individual IP addresses. While an interface on a router may be bi-directional, best paths in route tables are unidirectional. The best path for a destination in a route table directs a router to forward a packet addressed to the destination to a particular next hop specified for the path. But a best path does not specify an interface on a router at which a packet must be received. A receiving router typically can only influence a sending router's paths by route information exchanged through routing protocols.
In the Internet, an autonomous system (AS) is a collection of IP networks and routers, under the control of one or more entities that presents a common routing policy to the Internet. Within a single AS, Interior Gateway Protocols (IGPs) such as IGRP, EIGRP, OSPF, and RIP can be used to exchange route information. Among separate autonomous systems, Exterior Gateway Protocols (EGPs) such as EGP and BGP can be used to exchange route information.
BGP is the core routing protocol of the Internet. The primary function of a BGP speaker, which can be a router running BGP as one of its supported routing protocols, is to exchange network reachability information with other BGP speakers, including information about the list of autonomous systems involved in a path and other attributes related to the path.
A router at the boundary of an autonomous system that exchanges route information with a router in another autonomous system over external BGP (eBGP) is called a border router. The route information learned by a border router may be redistributed to other BGP speakers in the same autonomous system over internal BGP (iBGP). The route information learned by one routing protocol can also be redistributed to other routing protocols.
BGP can be used by an internetworked system to implement multihoming, which is a technique to maintain network performance and resiliency in the event of a failure or congestion condition affecting a single service provider by connecting the internetworked system to two or more service providers. A multihomed internetworked system can use a protocol like BGP running on one or more border routers to inform the rest of the Internet that it can be reached over multiple routes through two or more service providers.
A BGP speaker determines the best path among candidate paths over which a packet may possibly be forwarded by looking at a number of attributes relating to the paths. Such attributes include, for example, local preference, AS path and a multi exit discriminator (MED) metric. On routers from Cisco Systems, Inc, San Jose, Calif., a weight attribute can also be assigned to a candidate path and taken into account in path comparison. Once the best path for a destination is determined by a routing protocol such as BGP, a corresponding route is updated or created in a route table and, possibly, a previous route to the destination corresponding to a previous best path determination may be removed from the route table. This route typically contains information about the destination, next hop, interface, and metric, which may be mapped from attributes associated with the best path in the routing protocol.
A router's behaviors in routing protocols can be controlled by a routing policy. A routing policy influences the flow of route information exchanged through routing protocols. For example, for route information received by a router, a routing policy can filter candidate paths based on access lists, prefixes, communities, route maps, accept some paths, accept and modify some other paths, and reject still other paths. For route information to be sent by a router, a routing policy can filter paths based on the same constructs mentioned, allow some paths to be exposed to other routers, allow and modify some other paths, and prevent still other paths from being exchanged. In particular, attributes such as weight, local preference, AS path and multi-exit discriminator (MED) of a path can also be modified by the routing policy. Also, the mapping from best paths in a routing protocol to routes in a route table in terms of destination, next hop, interface and metric can be controlled by the routing policy.
Likewise, a router's behavior in forwarding packets can be controlled by policy-based routing (PBR). PBR binds with an interface and directs the interface how to handle a received packet. Specifically, whether a packet should be forwarded or dropped, where a packet should be forwarded, and how fields in a packet should be set, can all be directly controlled by PBR. Under PBR, packets to be forwarded are classified into different classes. The criteria for packet classification can be directly based on attributes associated with various layers in OSI model, not limited to just layer 3 IP attributes. For example, the classification, and further the forwarding, of a packet can be based on prefixes or applications associated with the packet. Packets that do not match criteria for any class are routed in a regular, non-PBR way, i.e., through a route table. For examples, a packet associated with an HTTP application from a content server can be in a class; a packet associated with a database system in a certain prefix in another class; a packet associated with VoIP in yet another class; and all other packets not belonging to any class defined under PBR are routed in a regular way through a route table. Different actions may be taken with respect to packets in different classes. For example, a VoIP packet may be specifically directed to a path that has low delay and little jitter. Furthermore, before forwarding, the VoIP packet may be specially marked by setting values of fields inside the packet.
The term “best path” ordinarily refers to a preferred path among all candidate paths for a destination in a Route Information Base (RIB) maintained by a routing protocol such as BGP. As used in this description and in the appended claims, the term “best path” may refer to a route—possibly corresponding to a best path in a RIB maintained by a routing protocol—in a route table learned through a routing protocol or advised under a routing policy. Alternatively, the term “best path” may also refer to a path specified by PBR for a class of packets based on a prefix or application.
In operation, establishing routing policy or PBR, which directly or indirectly influences the determination of best paths, is often based on non real-time information, e.g., statistics collected with respect to service providers, or types of interfaces—such as 10/100 Ethernet or OC12—used, or packet loss, delay and reachability information gathered by such tools as “traceroute.” Typically, policies are put in place for a lengthy time until some troubles are reported, e.g., by user complaints, or by some performance measuring tools, or until some configuration changes made somewhere in various autonomous systems impact the access of an internetworked system with the rest of the Internet. This heuristic and ad hoc approach to policy configuration is ill equipped to deal with a brownout condition relating to a service provider, where forwarding paths through the service provider's network experience a gradual deterioration, perhaps caused by some congested links within the service provider network.
The heuristic and ad hoc approach to policy configuration is also ill equipped to handle real-time traffic patterns, which may vary from time to time. For instance, a particular traffic pattern may overuse certain external interfaces, or exits, to a service provider, while under-use the others. Also, a type of traffic requiring short delay, low packet loss, or little jitter may instead be forwarded to a path that exhibits opposite characteristics, perhaps caused by some congested links within the service provider network.
While not a routing protocol, TCP is a connection-oriented transport protocol that is aware of congestion on a path. For example, TCP detects a drop in packets as congestion develops and immediately changes transmission parameters to compensate for the congestion (“backs off”). In some instances spurious back off occurs since the network itself might not be congested, but a packet might have been lost due to checksum corruption, heavy load on an host, etc. Thus the reduction in throughput by false back offs is often unnecessary.
To overcome this problem in TCP, an Explicit Congestion Notification (ECN) mechanism was developed, as described in IETF RFC 3168, the contents of which are herein incorporated by reference for all purposes as if originally set forth herein. ECN allows intermediary routers to explicitly communicate present or impending congestion condition to hosts. However, typically, the hosts still react to this notification by reducing the throughput of a TCP connection. This is undesirable because TCP may be handling a high throughput, time-critical application such as a real-time video stream. The problem can be avoided if, in place of taking a local remedial approach with respect to a single TCP application, overall traffic can instead be diverted or distributed in some optimal manner over all available external interfaces, e.g., by implementing changes in route tables, routing policies and PBRs.
Based on the foregoing, there is a need for an approach for dynamically and immediately updating best path based on real-time congestion feedback that does not suffer from limitations of prior approaches.